package demo;
import java.util.Arrays;
//实现一个堆
public class TestHeap {
    public int[] elem;//将堆中元素存放到一个数组中
    public int usedSize;//数组中元素的有效个数

    public TestHeap(){//将一个堆初始化能放入10个元素的数组，然后有效个数刚开始设置为0
        this.elem = new int[11];
        this.usedSize=0;
    }
    //创建一个堆
    public void createHeap(int[] array){
        //将array数组中的元素存放到这个堆中去
        for(int i =0;i<array.length;++i){
            this.elem[i] = array[i];
            this.usedSize++;
        }
        //接下来我们要将每一棵子树进行向下调整成一个大根堆
        //从最后一个子节点的父亲开始
        for(int p = (this.usedSize-1-1)/2;p>=0;p--){
            shiftDown(elem,p,this.usedSize);
        }
    }
    //交换两个元素的值
    public void swap(int[] array,int i,int j){
        int tmp = array[i];
        array[i] = array[j];
        array[j] = tmp;
    }
    public void shiftDown(int[] elem,int parent,int len){
        int child = 2*parent+1;//这个是父亲的左孩子
        //调整成大根堆
        while(child<len){
            //选择孩子中最大的那个与父亲进行比较
            if(child+1<len&&this.elem[child]<this.elem[child+1]){
                child++;
            }
            //如果孩子节点的值大于父亲节点的值那么就进行交换，否则父亲孩子节点进行更新
            if(this.elem[parent]<this.elem[child]){
                 swap(this.elem,child,parent);
            }else {
                break;
            }
            //父亲孩子节点进行更新
            parent = child;
            child = 2*parent+1;
        }
    }
    public void CheckGrow(){
            this.elem = Arrays.copyOf(this.elem,2*this.elem.length);
    }
    //堆中插入一个元素
    public void offer(int key){
        //如果满了就需要增容
        if(this.usedSize==this.elem.length){
            CheckGrow();
        }
        //在堆中插入一个元素的思路就是将元素插入到堆中最后的一个位置
        //然后将这个元素开始向上调整
        this.elem[usedSize] = key;//将元素插入到数组中最后一个位置
        //将这个元素向上调整
        shiftUp(this.elem,this.usedSize);
        this.usedSize++;
    }
    //向上调整
    public void shiftUp(int[] elem,int child){
        int parent = (child-1)/2;
        while(parent>=0){
            if(this.elem[parent]<this.elem[child]){
                swap(this.elem,parent,child);
            }else {
                break;
            }
            child = parent;
            parent = (child-1)/2;
        }
    }
    public boolean empty(){
        return this.usedSize==0;
    }
    //堆中删除元素-->堆中删除元素只能删除堆顶的元素
    public void poll(){
        //删除元素思路：将堆顶元素与堆中最后一个位置进行交换
        //然后将这个元素向下调整
        swap(this.elem,0,this.usedSize-1);//将堆顶元素与堆中最后一个位置进行交换
        //从0这个位置开始向下调整到this.usedSize-1
        this.usedSize--;
        shiftDown(this.elem,0,this.usedSize);
    }
    public int peek(){
        if(empty()){
            return -1;
        }else {
            return this.elem[0];
        }
    }
    //实现堆排序
    public void heapSort(){
        //从小到大排序我们要建立大堆
        //让其与最后一个元素交换之后然后向下调整
        for(int end = this.usedSize-1;end>=0;--end){
            swap(this.elem,0,end);
            shiftDown(this.elem,0,end);
        }
    }
}
